﻿//Copyright (c) 2010 Christopher E. S. King (http://chriskingconsulting.com)
//
//Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files 
// (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, 
// publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do 
// so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 
// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE 
// FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Reflection;
using System.Diagnostics.Contracts;
using System.Text.RegularExpressions;
using System.Collections;
using System.Globalization;
using System.IO;
using System.Xml;
using System.Xml.Linq;
using System.Runtime.InteropServices;

using King.Extensions;
using System.Diagnostics;

namespace King.Tree {

    public enum PreOrderMoveNextType {
        Unknown = 0,
        End,
        Up,
        Down,
        Next,
    }

    public interface IPreOrderEnumerable : IEnumerable {
        new IPreOrderEnumerator GetEnumerator();
    }
    public interface IPreOrderEnumerator : IEnumerator {
        new PreOrderMoveNextType MoveNext();
    }

    public interface IPreOrderEnumerable<T> : IEnumerable<T>, IPreOrderEnumerable {
        new IPreOrderEnumerator<T> GetEnumerator();
    }
    public interface IPreOrderEnumerator<T> : IEnumerator<T>, IPreOrderEnumerator {
    }

    public class ShiftReduce {

        private readonly Stack<int> m_childrenCount;
        private readonly Stack<object> m_stack;

        public ShiftReduce() {
            m_stack = new Stack<object>();
            m_stack.Push(null);
            m_childrenCount = new Stack<int>();
        }

        public void Shift(object value, bool isStart = false) {
            Contract.Assert(m_stack.Count > 0 || isStart);

            m_stack.Push(value);
            
            if (isStart)
                m_childrenCount.Push(0);

            m_childrenCount.Push(m_childrenCount.Pop() + 1);
        }
        public void Reduce(Func<object, Stack<object>, object> reduction) {
            Contract.Assert(m_childrenCount.Count > 0);

            var children = new Stack<object>();
            var count = m_childrenCount.Pop();
            while (count-- > 0)
                children.Push(m_stack.Pop());

            m_stack.Push(reduction(m_stack.Pop(), children));
        }
        public object Accept() {
            Contract.Assert(m_stack.Count == 1);
            Contract.Assert(m_childrenCount.Count == 0);

            return m_stack.Pop();
        }
    }

    [DebuggerDisplay("{m_value ?? \"(node)\"}")]
    [DebuggerTypeProxy(typeof(DebugProxy))]
    public class TreeNode : IEnumerable<object> {

        public class DebugProxy {

            private TreeNode m_treeNode;

            public DebugProxy(TreeNode treeNode) {
                m_treeNode = treeNode;
            }

            [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
            public object[] Children {
                get { return m_treeNode.ToArray(); }
            }
        }

        private object m_value;
        private IEnumerable<object> m_children;

        public TreeNode(object value, IEnumerable<object> children) {
            m_value = value;
            m_children = children;
        }

        public IEnumerator<object> GetEnumerator() {
            return m_children.GetEnumerator();
        }
        IEnumerator IEnumerable.GetEnumerator() {
            return GetEnumerator();
        }

        public override string ToString() {
            if (m_value == null)
                return null;
            return m_value.ToString();
        }
    }

    internal class PreOrderEnumerable<T> : IPreOrderEnumerable<T> {

        private class PreOrderEnumerator : IPreOrderEnumerator<T> {

            private PreOrderMoveNextType m_moveNext;
            private IEnumerator<object> m_enumerator;

            internal PreOrderEnumerator(IEnumerator<object> enumerator) {
                m_enumerator = enumerator;
                m_moveNext = PreOrderMoveNextType.Unknown;
            }

            public T Current {
                get { return (T)m_enumerator.Current; }
            }
            public PreOrderMoveNextType MoveNext() {
                if (m_enumerator.MoveNext() == false)
                    return PreOrderMoveNextType.End;

                if (m_enumerator.Current is PreOrderMoveNextType) {
                    m_moveNext = (PreOrderMoveNextType)m_enumerator.Current;

                    if (m_moveNext == PreOrderMoveNextType.Down)
                        m_enumerator.MoveNext();
                }

                var result = m_moveNext;
                m_moveNext = PreOrderMoveNextType.Next;

                return result;
            }
            public void Reset() {
                m_enumerator.Reset();
            }
            public void Dispose() {
                m_enumerator.Dispose();
            }
            object IEnumerator.Current {
                get { return Current; }
            }
            bool IEnumerator.MoveNext() {
                return MoveNext() != PreOrderMoveNextType.End;
            }
        }

        private IEnumerable<object> m_enumerable;

        internal PreOrderEnumerable(IEnumerable<object> enumerable) {
            m_enumerable = enumerable;
        }

        public IPreOrderEnumerator<T> GetEnumerator() {
            return new PreOrderEnumerator(m_enumerable.GetEnumerator());
        }
        IPreOrderEnumerator IPreOrderEnumerable.GetEnumerator() {
            return GetEnumerator();
        }
        IEnumerator<T> IEnumerable<T>.GetEnumerator() {
            return GetEnumerator();
        }
        IEnumerator IEnumerable.GetEnumerator() {
            return GetEnumerator();
        }
    }

    public static class TreeExtensions {
        public static TreeNode ToTree<T>(this IPreOrderEnumerable<T> source) {
            return (TreeNode)ToTree(
                source: (IPreOrderEnumerable)source, 
                reduction: (value, children) => 
                    new TreeNode(
                        value: (T)value, 
                        children: children
                    )
                );
        }
        public static object ToTree(this IPreOrderEnumerable source, Func<object, IEnumerable<object>, object> reduction) {
            var shiftReduce = new ShiftReduce();
            var enumerator = source.GetEnumerator();

            while (true) {
                var moveNext = enumerator.MoveNext();

                switch (moveNext) {
                    case PreOrderMoveNextType.Down:
                        shiftReduce.Shift(enumerator.Current, isStart: true);
                        break;

                    case PreOrderMoveNextType.Next:
                        shiftReduce.Shift(enumerator.Current);
                        break;

                    case PreOrderMoveNextType.Up:
                        shiftReduce.Reduce(reduction);
                        break;

                    case PreOrderMoveNextType.End:
                        break;

                    default:
                        throw new InvalidOperationException("MoveNext returned " + moveNext);
                }

                if (moveNext == PreOrderMoveNextType.End)
                    break;
            }

            return shiftReduce.Accept();
        }
        public static IPreOrderEnumerable<T> ToPreOrderEnumerable<T>(this IEnumerable source) {
            return new PreOrderEnumerable<T>(source.Cast<object>());
        }
    }
}
